(1) Field of Invention
The present invention relates to a secret sharing system and, more particularly, to a secret sharing system that provides non-statistical security.
(2) Description of Related Art
Secret sharing is a process by which secrets are distributed among an arbitrary number of servers. A concern in secret sharing is the possibility of an adversary who may corrupt a fixed portion of the servers. When the adversary corrupts a server, it learns all information stored on that server. The adversary can force corrupt servers to behave arbitrarily, irrespective of the protocol. Thus, it is imperative to implement a secure secret sharing protocol.
The secret sharing schemes of Literature Reference Nos. 5 and 14 (see the List of Incorporated Literature References) are non-mobile (i.e., they do not allow the set of servers holding the secret to change, as the present invention does). The scheme described in Literature Reference No. 9 only works for passive adversaries. In other words, it only works if corrupted servers follow the protocol.
The schemes of Literature Reference Nos. 16, 17, and 18 do not have optimal efficiency. Literature Reference Nos. 17 and 18 have communication complexity O(exp(n)), and Literature Reference No. 16 has communication complexity O(n3). Of the MPSS protocols listed above that are secure against active adversaries, the best communication complexity is O(n3) per secret (where n is the number of servers). The protocol described in U.S. application Ser. No. 14/449,115, which is hereby incorporated by reference as though fully set forth herein, had communication complexity O(n2) per secret.
Thus, a continuing need exists for a system having mobile proactive secret sharing (MPSS) functionality that provides non-statistical security with lower communication complexity than current systems.